#include<vector>
#include<unordered_map>
#include<bitset>
using namespace std;

class Solution {

private:

    bool reduce(int curTotal, int desiredTotal, std::bitset<20>& flags,unordered_map<unsigned long long,bool>& memory) {
        auto key = flags.to_ullong();
        if (memory.find(key) != memory.end())
            return memory[key];
        if (curTotal >= desiredTotal) {
            memory[key] = false;
            return memory[key];
        }
        bool flag = false;
        for (int i = 0; i < flags.size(); ++i) {
            if (flags[i]) continue;
            flags[i] = 1;
            if (!reduce(curTotal + i + 1, desiredTotal, flags, memory)) {
                flags[i] = 0;
                flag = true;
                break;
            }
            flags[i] = 0;
        }
        memory[key] = flag;
        return flag;
    }

public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal)
            return true;
        if ((maxChoosableInteger + 1) * maxChoosableInteger  < 2 * desiredTotal)
            return false;
        std::bitset<20>flags;
        flags.set();
        for (int i = 0; i < maxChoosableInteger; ++i)
            flags[i] = 0;
        unordered_map<unsigned long long, bool> memory;
        return reduce(0, desiredTotal, flags, memory);

    }
};